package com.zlk.algorithm.algorithm.sort.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

// 合并K个有序链表
// 测试链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
//合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
public class Code03_MergeKSortedLists {

      public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
          this.val = val;
        }
      }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *  合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
     * 数据范围：节点总数 0<=n<=5000  ,每个节点的val满足|val|<=1000
     * 要求时间复杂度 O（nlogN）
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a,b)->{
           return a.val-b.val;
        });
        for (int i = 0; i < lists.size(); i++) {
            ListNode h = lists.get(i);
            if (h != null) {
                heap.add(h);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }

        ListNode h = heap.poll();
        ListNode pre = h;
        if(pre.next!=null){
            heap.add(pre.next);
        }
        while (!heap.isEmpty()){
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if(cur.next!=null){
                heap.add(cur.next);
            }
        }
        return h;

    }

}
